Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 108 - Maximum sum / p108.cpp
blobc9246b20c21e9a02d82e8e049f99d86e9a27c282
1 #include <iostream>
2 #include <stdio.h>
4 using namespace std;
6 int m[203][203], dp[203][203];
8 int main(){
9 int n;
10 cin >> n;
11 memset(m, 0, sizeof(m));
12 memset(dp, 0, sizeof(dp));
13 for (int i=1; i<=n; ++i)
14 for (int j=1; j<=n; ++j)
15 cin >> m[i][j];
17 dp[1][1] = m[1][1];
18 for (int i=1; i<=n; ++i)
19 for (int j=1; j<=n; ++j)
20 dp[i][j] = dp[i][j-1] + m[i][j] + dp[i-1][j] - dp[i-1][j-1];
23 // cerr << "m es:\n";
24 // for (int i=0; i<=n+1; ++i){
25 // for (int j=0; j<=n+1; ++j)
26 // cerr << m[i][j] << " ";
27 // cerr << endl;
28 // }
29 // cerr << "\ndp es:\n";
30 // for (int i=0; i<=n+1; ++i){
31 // for (int j=0; j<=n+1; ++j)
32 // cerr << dp[i][j] << " ";
33 // cerr << endl;
34 // }
36 int max = m[0][0];
37 for (int i=n; i>=1; --i)
38 for (int j=n; j>=1; --j)
39 for (int k=1; k<=i; ++k)
40 for (int l=1; l<=j; ++l){
41 int a = dp[i][j] - dp[i-k][j] - dp[i][j-l] + dp[i-k][j-l];
42 if (a > max)
43 max = a;
45 cout << max << endl;